package 左哥算法.ch02二分;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

public class ch01_2_随机快排优化分区 {
    public int[] sortArray(int[] nums) {
        sort(nums, 0, nums.length - 1);
        return nums;
    }

    static Random random = new Random();

    public void sort(int[] nums, int l, int r) {
        if (l >= r) return;
        int v = nums[l + random.nextInt(r - l + 1)];
        int left = l;
        int right = r;
        for (int i = l; i <= right; i++) {
            if (nums[i] < v) {
                swap(nums, left++, i);
            } else if (nums[i] > v) {
                swap(nums, right--, i--);
            }
        }
        sort(nums, l, left - 1);
        sort(nums, right + 1, r);
    }

    public void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

    @Test
    public void test() {
        int[] arr = {1, 3, 5, 4, 2};
        sortArray(arr);
        System.out.println(Arrays.toString(arr));
    }
}
